// 将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。

// 暴露接口
function sortedArrayToBST(nums: number[]): TreeNode | null {
  if (nums.length < 1) {
    return null;
  }
  const midIndex: number = Math.floor(nums.length / 2);// 求解中索引
  const midNode: TreeNode = new TreeNode(nums[midIndex]);// 求解中节点
  midNode.left = sortedArrayToBST(nums.splice(0, midIndex));
  midNode.right = sortedArrayToBST(nums.splice(midIndex + 1, nums.length));
  return midNode;
}

// 二叉搜索树的中序遍历是升序的，因此本题等同于根据中序遍历的序列恢复二叉搜索树。
// 因此理论上我们可以以升序序列中的任一个元素作为根节点，
// 以该元素左边的升序序列构建左子树，
// 以该元素右边的升序序列构建右子树，这样得到的树就是一棵二叉搜索树。
// 又因为本题要求高度平衡，因此我们需要选择升序序列的中间元素作为根节点。

